The present invention relates to implementing finite field polynomial arithmetic expressions by Linear Feedback Shift Registers in error correcting coders. More in particular it relates to reducing or eliminating multipliers by modifying the functions in the finite field arithmetic expressions.
Linear Feedback Shift Registers or LFSRs may be considered one of the most widely applied fundamental logic or switching circuits in present day digital applications. Binary logic LFSRs are widely used as scramblers, descramblers, sequence generators and provide arithmetical execution in GF(2). Also known are non-binary LFSRs. Non-binary LFSRs are applied in for instance error correction coding applications, such as in Reed Solomon (RS) codes for implementing polynomial expressions over GF(n). A non-binary LFSR in a coder usually performs a polynomial calculation, more in particular a polynomial division. Non-binary LFSRs in coding are for instance described in Galois Field arithmetic as provided in the book: Error Control Coding, 2nd edition, by Shu Lin and Daniel J. Costello Jr.; Pearson Prentice Hall 2004.
Multi-valued LFSRs are used to generate for instance check symbols in coding and error correcting applications. A multi-valued LFSR, unless it strictly requires addition or subtraction will require multiplication over GF(n), wherein a multiplier usually represents a coefficient of a term in a polynomial over GF(n). Multiplication is a step in a multi-valued LFSR before an addition can be executed and requires additional circuitry in multi-valued LFSR apparatus. Accordingly this may require higher clock speeds in calculations and more circuitry, thus making prior art multi-valued LFSRs more expensive, more power consuming and less efficient.
Multipliers are known to make machine calculations slower and more expensive. Multipliers in LFSR appear because of coefficients of terms of factors in irreducible polynomials.
There are known efforts to make executing a multi-valued LFSR easier. For instance in United States patent application with publication number 20040054703 by Huber et al., filed on Oct. 22, 2003 and entitled: “Method and device for generating a pseudo-random sequence using a discrete logarithm,” (“Huber” hereafter) provide a method wherein a multiplication is replaced by calculating a discrete logarithm in a multi-valued LFSR and wherein the multi-valued LFSR the addition function in a Fibonacci LFSR is replaced by a discrete logarithm function and a multiplication is replaced by an addition. The method as disclosed in “Huber” does not address the issues of clock speed and additional components.
Accordingly methods and apparatus for implementing a multi-valued LFSR using no or a reduced number of multipliers are required.